package 每日一题;

import publicClass.TreeNode;

import java.util.HashSet;

/**
 * 1261. 在受污染的二叉树中查找元素
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给出一个满足下述规则的二叉树：
 *
 * root.val == 0
 * 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
 * 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
 * 现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
 *
 * 请你先还原二叉树，然后实现 FindElements 类：
 *
 * FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
 * bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
 *
 */
public class T1261_在受污染的二叉树中查找元素 {


    class FindElements {
        HashSet<Integer> hashSetTreeValue;

        //还原二叉树  使用深度递归遍历即可 ,为了加速查询 使用set 记录存在的值
        public FindElements(TreeNode root) {
            hashSetTreeValue = new HashSet<>();
            //深度递归 遍历 恢复整棵树
            dfs(root, 0);

        }

        public void dfs(TreeNode node, int value) {
            if (null != node) {
                node.val = value;
                hashSetTreeValue.add(value);
                dfs(node.left, value * 2 + 1);
                dfs(node.right, value * 2 + 2);
            }
        }

        public boolean find(int target) {
            return hashSetTreeValue.contains(target);
        }
    }

}


